// Package order_by_hot No-2-jump
// @Title order_by_hot
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/27 15:45
// @Create  2021/9/27 15:45
package _1_DP

import "fmt"

/**
爬楼梯算法  一次可以爬1阶 或者2阶
*/

func Jump(a int) {

	//fmt.Println(dpArrayProcess(a))
	fmt.Println(compressDP(a))
}

// 使用DP状态数组实现动态规划
func dpArrayProcess(a int) int {
	if a < 2 {
		return a
	}
	dp := make([]int, a+1)
	dp[0] = 1
	dp[1] = 1
	for i := 2; i <= a; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[a]
}

// 状态压缩算法解决
func compressDP(a int) int {
	if a < 2 {
		return a
	}
	pre, cur, ans := 0, 1, -1
	for i := 0; i < a; i++ {
		ans = cur + pre
		cur, pre = ans, cur
	}
	return ans
}

// 如果可以有m中方式爬楼梯呢？
func plusDPJump(n, m int) int {
	if n <= 0 {
		return 0
	}
	return 0
}
